/* 
 * File:   Graph.cpp
 * Author: chadijir
 * 
 * Created on September 26, 2010, 12:53 PM
 */

#include "Graph.h"
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include "settings.h"

using namespace std;

/**
 * Inits all static fields and srand
 */
Graph::Graph() {
    minEdgeWeight = 0;
    graphRegularity = 0;
    maxCutWeight = 0;
    maxCutWeightNode = 0;
    nodeCount = 0;
    srand(time(NULL));
}

/**
 * Copies graph, not completed, matrix copying is not implemented
 * @param orig
 */
Graph::Graph(const Graph& orig) {
    minEdgeWeight = orig.minEdgeWeight;
    graphRegularity = orig.graphRegularity;
    maxCutWeight = orig.maxCutWeight;
    nodeCount = orig.nodeCount;
    //TODO copy matrix
}

/**
 * Deletes matrix
 */
Graph::~Graph() {
    unsigned int i;
    for (i = 0; i < getNodeCount(); i++) {
        delete [] incidenceMatrix[i];
    }
    delete [] incidenceMatrix;
}

unsigned int Graph::getRegularity() const {
    return graphRegularity;
}

unsigned int Graph::getMinEdgeWeight() const {
    return minEdgeWeight;
}

unsigned int Graph::getMaxCutWeight() const {
    return maxCutWeight;
}

unsigned int Graph::getMaxCutWeightNode() const {
    return maxCutWeightNode;
}

unsigned int Graph::getNodeCount() const {
    return nodeCount;
}

/**
 *
 * @Deprecated
 * @return random number from <1, Graph::MAX_WEIGHT>
 */
unsigned int Graph::getRandomWeight() {
    return rand() % MAX_WEIGHT + 1;
}

/**
 * Shorthand for accessing matrix, bound checking implemented
 * @param i
 * @param j
 * @return Value on i, j position
 */
unsigned int Graph::getValue(unsigned int i, unsigned int j) {
    if (i >= nodeCount || j >= nodeCount) {
        return -1;
    }
    return incidenceMatrix[i][j];
}

/**
 * Method that counts graph regularity, max cut weight and max cut weight node.
 * It is slower than counting those values while reading graph instance from
 * input, but can be performed when graph is deserialized from network.
 */
void Graph::countCharacteristics() {
    if (incidenceMatrix == NULL) {
        return;
    }

    unsigned int i, j, value, nodeWeight;
    minEdgeWeight = MAX_WEIGHT;
    maxCutWeight = nodeCount*MAX_WEIGHT;

    for (i = 0; i < nodeCount; i++) {
        nodeWeight = 0;
        for (j = 0; j < nodeCount; j++) {
            value = incidenceMatrix[i][j];
            if (value > 0 && value < minEdgeWeight) minEdgeWeight = value; // min edge weight retrieval
            nodeWeight += value;
            // let's get regularity (aka in first row, count numbers other than zeros)
            if (i == 0 && incidenceMatrix[i][j] > 0) graphRegularity++;
        }

        if (nodeWeight < getMaxCutWeight()) {
            maxCutWeight = nodeWeight; // do we have a new max cut weight?
            maxCutWeightNode = i; // which node has the new max cut weight?
        }
    }
}

/**
 * Allocates matrix.
 * @param nc
 */
void Graph::initMatrix(const unsigned int nc) {

    nodeCount = nc;
    unsigned int i = 0;
    incidenceMatrix = new unsigned int * [nc];
    for (i = 0; i < nc; i++) { // allocate rows
        incidenceMatrix[i] = new unsigned int [nc];
    }

}

/**
 * Input read. Matrix is allocated via initMatrix and characteristics are
 * counted by method
 * countCharacteristics().
 * @param in
 * @param graph
 * @return
 */
istream & operator>>(istream &in, Graph &graph) {

    in >> graph.nodeCount;
    unsigned int nc = graph.getNodeCount();
    unsigned int totalSize = nc*nc;
    unsigned int i;
    unsigned int value;

    graph.initMatrix(nc);

    for (i = 0; i < totalSize; i++) { // coords: i/nc, i%nc
        in >> value;
        if (i / nc > i % nc) continue; // skip values under main diagonal (they are the same as those above)

        graph.incidenceMatrix[i / nc][i % nc] = value;
        graph.incidenceMatrix[i % nc][i / nc] = value;
    }
    graph.countCharacteristics();
    return in;
}

/**
 * Graph is recreated from char buffer. Node count is sqrt of bufferSize.
 * @param buffer - char representation of graph
 * @param bufferSize - size of filled part in buffer
 * @return always should be zero.
 */
int Graph::deserialize(unsigned char * buffer, const int bufferSize) {
    int nc = sqrt(bufferSize);
    int i;
    unsigned int value;

    initMatrix(nc);

    for (i = 0; i < bufferSize; i++) {
        value = (unsigned int)buffer[i];
        if (i / nc > i % nc) continue;

        incidenceMatrix[i / nc][i % nc] = value;
        incidenceMatrix[i % nc][i / nc] = value;
    }

    countCharacteristics();
    return 0;
}

/**
 * Fancy output containing all information about this graph including incidence
 * matrix.
 * @param out
 * @param graph
 * @return
 */
ostream & operator<<(ostream &out, const Graph &graph) {

    out << "Graph input" << endl;
    out << setw(40) << setfill('=') << ' ' << endl;

    out << setfill(' ') << "Nr. of nodes: " << graph.getNodeCount() << endl;
    out << "Regularity: " << graph.getRegularity() << endl;
    out << "Min edge weight: " << graph.getMinEdgeWeight() << endl;
    out << "Max cut weight: " << graph.getMaxCutWeight() << endl;
    out << "Max cut weight node: " << graph.getMaxCutWeightNode() << endl;

    unsigned int i;
    unsigned int nc = graph.getNodeCount();
    for (i = 0; i < nc; i++) {
        out << setw(5) << i << ": ";
        for (unsigned int j = 0; j < nc; j++) {
            out << setw(3) << graph.incidenceMatrix[i][j] << " ";
        }
        out << endl;
    }
    return out;
}

/**
 * Serializes graph matrix into char buffer
 * @param buffer - where the graph will be stored
 * @param bufferSize - total size of buffer, if graph is too big, -1 is returned
 * @return -1 if graph can not fit buffer, size of filled portion of buffer otherwise
 */
int Graph::serialize(unsigned char * buffer, const int bufferSize) {
    unsigned int i, j;
    unsigned int nc = nodeCount;
    if (nc * nc > (unsigned int) (bufferSize - 1)) {
        return -1;
    }

    for (i = 0; i < nc; i++) {
        for (j = 0; j < nc; j++) {
            buffer[i * nc + j] = incidenceMatrix[i][j];
        }
    }

    return nc*nc;
}
